#include <bits/stdc++.h>

using namespace std;

int dp[33000],c[100][100],v[100][100],tot[100],N,n,m,s[100];
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)tot[i]=1;
    for(int i=1;i<=n;i++){
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        if(t3==0){
            N++;
            s[i]=N;
            c[N][1]=t1;
            v[N][1]=t1*t2;
        }
        else{
            tot[s[t3]]++;
            c[s[t3]][tot[s[t3]]]=t1+c[s[t3]][1];
            v[s[t3]][tot[s[t3]]]=t1*t2+v[s[t3]][1];
            if(tot[s[t3]]==3){
            tot[s[t3]]++;
            c[s[t3]][tot[s[t3]]]=t1+c[s[t3]][2];
            v[s[t3]][tot[s[t3]]]=t1*t2+v[s[t3]][2];
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=m;j>=0;j--){
            for(int k=1;k<=tot[i];k++){
                if(j>=c[i][k])dp[j] = max(dp[j],dp[j-c[i][k]]+v[i][k]);
            }
        }
    }
    cout<<dp[m];
    return 0;
}
